//
// Created by xili on 2024/9/13 14:17.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    string largestMultipleOfThree(vector<int> &digits) {
        vector<int> val(10), modd(3);
        int sum = 0;
        for (auto &d: digits)val[d]++, modd[d % 3]++, sum += (d % 3);
        int del = 0, cnt = 0;
        if (sum % 3 == 0) {
            //do nothing
        } else if (sum % 3 == 1) {
            // one 1 or two 2
            if (modd[1] >= 1)del = 1, cnt = 1;
            else if (modd[2] >= 2)del = 2, cnt = 2;
            else del = -1;
        } else {
            //one 2 or two 1
            if (modd[2] >= 1)del = 2, cnt = 1;
            else if (modd[1] >= 2)del = 1, cnt = 2;
            else del = -1;
        }
        string res;
        if (del == -1)return "";
        for (int i = 0; i < 10; i++) {
            while ((i % 3) == del && cnt && val[i])cnt--, val[i]--;
        }
        for (int i = 9; i >= 0; i--) {
            while (val[i])res.push_back(i + '0'), val[i]--;
        }
        //special judge
        if (res.size() >= 2 && res[0] == '0')return "0";
        return res;
    }
};